ABC248 C - Dice Sum

https://atcoder.jp/contests/abc248/tasks/abc248_c

提出

code: python

import itertools

n, m, k = map(int, input().split())

# 2 3 4

# A(A1, A2) 1 <= A1, A2 <= 3

# TODO: 探索を打ち切る

# TODO: itertools.product 使わない

ans = 0

for p in itertools.product(i for i in range(1, m+1), repeat=n):

if (sum(p) <= k):

ans += 1

print(ans % 998244353)

解答

code: python

n, m, k = map(int, input().split())

# 2 3 4

# n: 組み合わせ

# m: 最大の数

# k: 総和の最大

mod = 998244353

# dpij : 数列の i 番目まで決めて、総和が j であるものの個数

# dpn1 + dpn2 + ⋯ + dpnk を求める

dp = [0 * (k + 1) for _ in range(n + 1)]

# 数列の 0 番目まで決めて、総和が 0 の個数

dp00 = 1

#「 i番目 Aiまで決めて、総和が j の数列」から、i+1 番目の要素 Ai+1 を決めたときの遷移を考える

for i in range(n):

for ik in range(k):

for im in range(1, m + 1): # Ai + 1 の数

if ik + im > k: # k 以上はいらない

break

dpi + 1ik + im += dpiik # 数列の i 番目まで決めて、総和が j であるものの数

dpi + 1ik + im %= mod

# print(dp)

# 1, 0, 0, 0, 0], 0, 1, 1, 1, 0, [0, 0, 1, 2, 3

print(sum(dp-1) % mod)

テーマ

#dp

メモ

【AtCoder解説】PythonでABC248のA,B,C,D,E,F問題を制する！

提出

code: python

n, m, k = map(int, input().split())

# n: 組み合わせ

# m: 最大の数

# k: 総和の最大

# O(pow(m, n))

# (3, 1) -> (2, 1)...